      1  /**

      2     The sort method of this class sorts an array, using the heap

      3     sort algorithm.

      4  */

      5  public class HeapSorter

      6  {

      7     /**

      8        Sorts an array, using selection sort.

      9        @param a the array to sort

     10     */

     11     public static void sort(int[] a)

     12     {

     13        int n = a.length - 1;

     14        for (int i = (n - 1) / 2; i >= 0; i--)

     15        {

     16           fixHeap(a, i, n);

     17        }

     18        while (n > 0)

     19        {

     20           ArrayUtil.swap(a, 0, n);

     21           n--;

     22           fixHeap(a, 0, n);

     23        }

     24     }

     25

     26     /**

     27        Ensures the heap property for a subtree, provided its

     28        children already fulfill the heap property.

     29        @param a the array to sort

     30        @param rootIndex the index of the subtree to be fixed

     31        @param lastIndex the last valid index of the tree that

     32        contains the subtree to be fixed

     33     */

     34     private static void fixHeap(int[] a, int rootIndex, int lastIndex)

     35     {

     36        // Remove root

     37        int rootValue = a[rootIndex];

     38

     39        // Promote children while they are larger than the root

     40

     41        int index = rootIndex;

     42        boolean more = true;

     43        while (more)

     44        {

     45           int childIndex = getLeftChildIndex(index);

     46           if (childIndex <= lastIndex)

     47           {

     48              // Use right child instead if it is larger

     49              int rightChildIndex = getRightChildIndex(index);

     50              if (rightChildIndex <= lastIndex

     51                    && a[rightChildIndex] > a[childIndex])

     52              {

     53                 childIndex = rightChildIndex;

     54              }

     55

     56              if (a[childIndex] > rootValue)

     57              {

     58                 // Promote child

     59                 a[index] = a[childIndex];

     60                 index = childIndex;

     61              }

     62              else

     63              {

     64                 // Root value is larger than both children

     65                 more = false;

     66              }

     67           }

     68           else

     69           {

     70              // No children

     71              more = false;

     72           }

     73        }

     74

     75        // Store root value in vacant slot

     76        a[index] = rootValue;

     77     }

     78

     79     /**

     80        Returns the index of the left child.

     81        @param index the index of a node in this heap

     82        @return the index of the left child of the given node

     83     */

     84     private static int getLeftChildIndex(int index)

     85     {

     86        return 2 * index + 1;

     87     }

     88

     89     /**

     90        Returns the index of the right child.

     91        @param index the index of a node in this heap

     92        @return the index of the right child of the given node

     93     */

     94     private static int getRightChildIndex(int index)

     95     {

     96        return 2 * index + 2;

     97     }

     98  }